// 给定一个数组nums，要求计算出数组中的逆序对的总数
// 逆序对：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对

// 思路，利用归并排序，分为分解和合并两个过程，在合并的时候比较两个有序数组可以确定逆序对的数量
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)

function reversePairs(arr) {
    let ans = 0
    function mergeSort(arr) {
        if (arr.length <= 1) {
            return arr
        }
        let mid = Math.floor(arr.length / 2)
        const leftArr = mergeSort(arr.slice(0, mid))
        const rightArr = mergeSort(arr.slice(mid))
        return merge(leftArr, rightArr)
    }

    function merge(leftArr, rightArr) {
        let index1 = 0
        let index2 = 0
        let res = []
        while (index1 < leftArr.length && index2 < rightArr.length) {
            if (leftArr[index1] <= rightArr[index2]) {
                res.push(leftArr[index1])
                index1++
            } else {
                ans += leftArr.length - index1
                res.push(rightArr[index2])
                index2++
            }
        }
        // 这里小心别漏了这两个情况
        if (index1 < leftArr.length) {
            res = res.concat(leftArr.slice(index1))
        }
        if (index2 < rightArr.length) {
            res = res.concat(rightArr.slice(index2))
        }
        return res
    }
    mergeSort(arr)
    return ans
}

let arr = [7, 5, 6, 4];

console.log(reversePairs(arr))